package com.ruanruan.structure.graph.dfs;

import com.ruanruan.structure.graph.AdjList;
import com.ruanruan.structure.graph.Graph;

/**
 * 环检测
 */
public class CycleDetection {


    private final Graph G;

    private final boolean[] visited;

    private boolean isCycle = false;

    public CycleDetection(Graph G) {
        this.G = G;
        this.visited = new boolean[G.V()];

        for (int v = 0; v < G.V(); v++) {
            if (!visited[v]) {
                dfs(v, v);
            }
        }
    }

    private void dfs(int v, int parent) {
        visited[v] = true;

        for (int w : G.adj(v)) {
            if (!visited[w]) {
                dfs(w, v);
            } else if (w != parent) {
                isCycle = true;
            }
        }
    }

    public boolean isCycle() {
        return isCycle;
    }

    public static void main(String[] args) {
        CycleDetection detection = new CycleDetection(new AdjList("resources/graph/g_cc.txt"));
        System.out.println(detection.isCycle());
    }
}
